package leetcode.code1622;

public class Fancy {

	public int N = (int) 1e5 + 1;

	int[] num;
	int[] add;
	int[] mul;
	int end;

	int mod = (int) 1e9 + 7;

	public Fancy() {
		num = new int[N + 1];
		add = new int[(N + 1) << 1];
		mul = new int[(N + 1) << 1];
		for (int i = 0; i < mul.length; i++) {
			mul[i] = 1;
		}
		end = 1;
	}

	public void append(int val) {
		num[end++] = val;
	}

	public void addAll(int inc) {
		add(1, end - 1, inc, 1, N, 1);
	}

	public int add(int a, int b) {
		return (int) ((1l * a + 1l * b) % mod);
	}

	public void add(int L, int R, int val, int l, int r, int root) {
		if (L > R) {
			return;
		}
		if (L <= l && r <= R) {
			add[root] = add(add[root], val);
		} else {
			process(root);
			int mid = ((r - l) >> 1) + l;
			if (L <= mid)
				add(L, R, val, l, mid, root << 1);
			if (R > mid)
				add(L, R, val, mid + 1, r, root << 1 | 1);
		}
	}

	private void process(int root) {
		mul[root << 1] = mul(mul[root], mul[root << 1]);
		mul[root << 1 | 1] = mul(mul[root], mul[root << 1 | 1]);
		add[root << 1] = mul(mul[root], add[root << 1]);
		add[root << 1 | 1] = mul(mul[root], add[root << 1 | 1]);
		mul[root] = 1;
		add[root << 1] = add(add[root], add[root << 1]);
		add[root << 1 | 1] = add(add[root], add[root << 1 | 1]);
		add[root] = 0;

	}

	public void multAll(int m) {
		mul(1, end - 1, m, 1, N, 1);
	}

	private void mul(int L, int R, int val, int l, int r, int root) {
		if (L > R) {
			return;
		}
		if (L <= l && r <= R) {
			add[root] = mul(add[root], val);
			mul[root] = mul(mul[root], val);
		} else {
			process(root);
			int mid = ((r - l) >> 1) + l;
			if (L <= mid)
				mul(L, R, val, l, mid, root << 1);
			if (R > mid)
				mul(L, R, val, mid + 1, r, root << 1 | 1);
		}
	}

	private int mul(int a, int b) {
		return (int) (1l * a * b % mod);
	}

	public int getIndex(int idx) {
		if (idx >= end - 1) {
			return -1;
		}
		return query(idx + 1);
	}

	private int query(int idx) {
		int n1 = num[idx];
		int id = query(idx, 1, N, 1);
		return add(mul(n1, mul[id]), add[id]);
	}

	private int query(int idx, int l, int r, int root) {
		if (l == r) {
			return root;
		} else {
			process(root);
			int mid = ((r - l) >> 1) + l;
			if (idx <= mid) {
				return query(idx, l, mid, root << 1);
			} else {
				return query(idx, mid + 1, r, root << 1 | 1);
			}
		}
	}

	public static void main(String[] args) {
		Fancy fancy = new Fancy();
		fancy.addAll(1); // 奇妙序列：[2+3] -> [5]
//		fancy.append(2); // 奇妙序列：[2]
//		fancy.addAll(3); // 奇妙序列：[2+3] -> [5]
//		fancy.append(7); // 奇妙序列：[5, 7]
//		fancy.multAll(2); // 奇妙序列：[5*2, 7*2] -> [10, 14]
//		System.out.println(fancy.getIndex(0)); // 返回 10
//		fancy.addAll(3); // 奇妙序列：[10+3, 14+3] -> [13, 17]
//		fancy.append(10); // 奇妙序列：[13, 17, 10]
//		fancy.multAll(2); // 奇妙序列：[13*2, 17*2, 10*2] -> [26, 34, 20]
//		System.out.println(fancy.getIndex(0)); // 返回 26
//		System.out.println(fancy.getIndex(1)); // 返回 34
//		System.out.println(fancy.getIndex(2)); // 返回 20

	}
}
